package com.up.interview.dataStructuresAndAlgorithms;

import com.up.interview.dataStructuresAndAlgorithms.dataS.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * @author: liuchengjun
 * @title: DFS
 * @projectName: 海联技术中台V2.0
 * @depart 软件事业部
 * @description:
 * @date: 2025/10/23/周四 15:39 (星期四)
 * @since V2.0
 */
public class DFS {

    /**
     * 按照一定的筛选条件往下寻找，失败则返回上个节点继续寻找
     * 核心：画出递归树   明确递归结束条件  明确每个节点的状态
     */


    /**
     * 树结构:
     *        1
     *       / \
     *      2   3
     *     / \
     *    4   5
     *
     * DFS遍历（前序）:
     * 1 → 往左走 → 2 → 往左走 → 4 → 回溯 → 5 → 回溯 → 3
     * 顺序: 1, 2, 4, 5, 3
     * @param node
     */
    void dfs(TreeNode node) {
        if (node == null) return;

        System.out.print(node.getVal());  // 访问
        dfs(node.getLeft());              // 递归左
        dfs(node.getRight());             // 递归右
    }


    /**
     * 括号生成
     *  问题类型：寻找问题的解（（（）））
     *  思路：DFS深度优先搜索
     *  - 画出递归树
     *  - -  递归结束条件（剪枝，控制结束） 递归体：每个节点可以做什么选择   回溯：回溯到上个节点状态
     *
     * @param n
     * @return
     */
    public List<String> generateParenthesis(int n) {
        List<String> res = new ArrayList<>();
        //处理字符串拼接
        StringBuilder sb = new StringBuilder();
        //当前可以适应的左右括号数
        int left = n;
        int right = n;
        dfs(left, right, sb, res);
        return res;
    }



    public void dfs(int left,int right,StringBuilder sb,List<String> res){
        //递归结束条件：括号使用完和有括号数>左括号
        if(left == 0 && right == 0){
            res.add(sb.toString());
            return;
        }
        if(left > right){
            return;
        }
        //递归体：每个节点在限制内都可以选择左右括号
        if(left > 0){
            sb.append("(");
            dfs(left-1,right,sb,res);
            //回溯：处理结束后需回溯到上个节点状态（取消当前选择）
            sb.deleteCharAt(sb.length()-1);
        }
        if(right > 0){
            sb.append(")");
            dfs(left,right-1,sb,res);
            //回溯：处理结束后需回溯到上个节点状态（取消当前选择）
            sb.deleteCharAt(sb.length()-1);
        }
    }


}
